import java.util.*;

//解法 ： 暴力回溯
//给定图 ， 给定颜色 ， 给出是否能解
public class Solution_2 {
    Graph graph ;
    boolean[] flags ;
    int flagCnt = 0 ;
    int pointNub = 0 ;
    boolean stopFlag = false ;

    //color 代表颜色  pos代表哪一个点要加颜色   status加颜色前的状态
    int push_color(int color, int pos, int status){
        color-- ;
        //(pos-1)*2 为该点对应的颜色状态的低位,也是偏移量
        int v = pos*2 ;
        //将颜色偏移到该点对应的位置
        color = color<<v ;
        //相并合并状态
        status = status|color ;
        return status ;
    }

    //colorPoint:这个递归过程要上4色的所有点  cnt：现在已经上色到哪一个点    colorStatus：用来收集上完色的状态传回到主函数
    void dfs_for_color(List<Integer> colorPoint,int cnt,int status,List<Integer> colorStatus){
        //当前要涂的点的编号
        int point = colorPoint.get(cnt) ;
        //System.out.println(point);
        //标记当前的点
        flags[point] = true ;
        //获取这个点周围的颜色
        boolean[] usedColor =graph.getAroundColors(point) ;
        for(int i=1;i< usedColor.length;i++){
            //找到可以用的颜色填上
            if(!usedColor[i]){
                graph.nodeColor[point] = i ;
                //将这个点的颜色注入到status中,原状态不可变 另开一个
                int temp = push_color(i,point,status) ;
                if(cnt==colorPoint.size()-1){
                    colorStatus.add(temp);
                }else{
                    dfs_for_color(colorPoint,cnt+1,temp,colorStatus);
                }
                graph.nodeColor[point] = 0 ;
            }
        }
        //解锁
        flags[point] = false ;
    }

    //去色
    private void outColor(List<Integer> points) {
        for(Integer point : points){
            flags[point] = false ;
            graph.nodeColor[point] = 0 ;
        }
    }

    //上色
    private void onColor(int status,List<Integer> points) {
        for(Integer point : points){
            //通过位运算将对应位置的color提取出来
            int color = (status>>((point-1)*2))&3 ;
            //将该点标记为已经用了
            flags[point] = true ;
            //给点涂色
            graph.nodeColor[point] = ++color ;
        }
    }

    List<Integer> removeNubEqu(List<Integer> list){
        Set<Integer> set = new LinkedHashSet<>() ;
        set.addAll(list);
        list.clear();
        list.addAll(set) ;
        return list ;
    }

    void dfs_for_ans(List<Integer> father,int status){
        //首先找到与上一个点集连接的所有点
        List<Integer> child = new ArrayList<>() ;
        for(int item : father){
            //遍历与这个点连接的所有边
            for(int i=graph.head[item];i!=-1;i=graph.edges[i].next){
                //如果这条边所指向的点没有被用过则加入
                int next = graph.edges[i].to ;
                if(!flags[next]){
                    child.add(next) ;
                }
            }
        }

        //除重
        removeNubEqu(child) ;
        //找完所有点之后准备给子点上色，上色前要提前算出所有的可能以便于回溯
        //上色的依据得根据 父节点群 与 兄弟节点群 的限制来上色
        //其中父节点群在每次上色都不会有改动 ， 但是对于兄弟节点群来说由于顺序的不同会使得后续上色的节点不同
        //因此这里要采用递归的方法 来给兄弟节点群来计算出上色的可能性

        //颜色状态的保存方法：将所有点的颜色状态保存在一个32位的int类型里面  每一个节点对应最多有4种颜色因此可以用两位代表一个节点的颜色状态
        //                 因此 32/2 = 16 最多可以同时保存16个节点的颜色 所以该算法的最大涂色节点数位 16

        //用于接收 兄弟群的所有涂色集
        if(child.size()==0){
            System.out.println("hahah");
        }

        List<Integer> colorStatus = new ArrayList<>();
        dfs_for_color(child,0,status,colorStatus) ;

        //开始染色
        for(int state : colorStatus){
            //将item翻译然后并且涂色
            onColor(state,child) ;

            //如果把孩子的色都染成功就直接有解了;
            if(flagCnt+child.size()==pointNub){
                graph.printNodeColor();
                stopFlag = true ;
            }

            //停止递归
            if(!stopFlag){
                flagCnt+=child.size() ;
                dfs_for_ans(child,state) ;
                flagCnt-=child.size() ;
            }else{
                return ;
            }
            //染色失败就恢复现场
            outColor(child) ;
        }
    }

    void initSolution(int nodeNub ,int maxEdges ,int colorNub ){
        pointNub = nodeNub ;
        //整一个flag出来
        flags = new boolean[nodeNub];
        //建一个链式前向星
        graph = new Graph(nodeNub,maxEdges,colorNub) ;
        //提前标记第一个点的颜色
        graph.nodeColor[0] = 1  ;
        //已经使用
        flags[0] = true ;
        flagCnt++ ;
        List<Integer> father = new ArrayList<>() ;
        father.add(0) ;
        //开始深搜答案
        graph.printGraph();
        dfs_for_ans(father,1);
        System.out.println("end");
    }

    public static void main(String[] args) {
        Solution_2 solution2 = new Solution_2() ;
        solution2.initSolution(10,50,4);
    }
}
